from typing import DefaultDict


class Solution:
    def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:

        hash = 0
        mod = 1000000007
        base = 13131
        mp = DefaultDict(int)
        p = len(s) // k
        for i, v in enumerate(s):
            hash = (hash * base + ord(v)) % mod
            if (i + 1) % p == 0:
                mp[hash] += 1
                hash = 0
        for i, v in enumerate(t):
            hash = (hash * base + ord(v)) % mod
            if (i + 1) % p == 0:
                mp[hash] -= 1
                hash = 0
        return all(v == 0 for k, v in mp.items())


s = Solution()
print(s.isPossibleToRearrange("tws", "wts", 1))
print(s.isPossibleToRearrange(s="abcd", t="cdab", k=2))
print(s.isPossibleToRearrange(s="aabbcc", t="bbaacc", k=3))
print(s.isPossibleToRearrange(s="aabbcc", t="bbaacc", k=2))
